#include <iostream>
#include <queue>
using namespace std;

struct Node {
  char val;
  Node *left, *right;
  Node() : val(' '), left(nullptr), right(nullptr) {}
  Node(int val) : val(val), left(nullptr), right(nullptr) {}
  Node(int val, Node *left, Node *right) : val(val), left(left), right(right) {}
};

Node *create() {
  char data;
  cin >> data;
  if (data == '#')
    return nullptr;
  else {
    Node *t = new Node();
    t->val = data;
    t->left = create();
    t->right = create();
    return t;
  }
}

void preOrder(Node *t) {
  if (t) {
    cout << t->val << " ";
    preOrder(t->left);
    preOrder(t->right);
  }
}

void inOrder(Node *t) {
  if (t) {
    inOrder(t->left);
    cout << t->val << " ";
    inOrder(t->right);
  }
}

void postOrder(Node *t) {
  if (t) {
    postOrder(t->left);
    postOrder(t->right);
    cout << t->val << " ";
  }
}

void levelOrder(Node *t) {
  if (t == nullptr)
    return;

  queue<Node *> q;
  q.push(t);
  while (!q.empty()) {
    Node *head = q.front();
    cout << head->val << " ";
    if (head->left)
      q.push(head->left);
    if (head->right)
      q.push(head->right);
    q.pop();
  }
}

Node *revertTree(Node *t) {
  if (!t)
    return t;

  Node *temp = t->left;
  t->left = revertTree(t->right);
  t->right = revertTree(temp);
  return t;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    Node *t = create();
    revertTree(t);
    preOrder(t);
    cout << endl;
    inOrder(t);
    cout << endl;
    postOrder(t);
    cout << endl;
    levelOrder(t);
  }

  return 0;
}